package com.demo.sort;

import com.demo.sort.base.SortBase;

/**
 * 插入排序   小 -> 大    A(待插入值)  B(比较值)
 * 思路:
 * 首先明确每次选择前的子序都是排序好的
 * 1. 取出A,依次向前比较并把B向后移动(B > A)
 * 2. 当遇到B比A小的则停止并替换值(B = A)
 * 分析:
 * 时间复杂度    O(n^2)
 * 空间复杂度    O(1)
 **/
public class InsertionSort extends SortBase {

    public int[] sort(int[] init) {
        for(int i = 1, len = init.length, j; i < len; i++) {
            j = i;
            int temp = init[i];
            while (j > 0 && temp < init[j - 1]) {
                init[j] = init[j - 1];
                j--;
            }
            if (j != i) {
                init[j] = temp;
            }
        }
        return init;
    }
}
